package _interview100;

/**
 * 121. 买卖股票的最佳时机
 */
public class No121 {
    private int[] prices;

    /*
      一、状态机DP
     */

    /**
     * 1.递归
     */
    public int maxProfit11(int[] prices) {
        this.prices = prices;
        int n = prices.length;
        return dfs(n - 1, 1, 0);
    }

    private int dfs(int i, int j, int hold) {
        if (j < 0) return Integer.MIN_VALUE;
        else if (i < 0) return hold == 0 ? 0 : Integer.MIN_VALUE;
        else if (hold == 0) return Math.max(dfs(i - 1, j, 0), dfs(i - 1, j - 1, 1) + prices[i]);
        else return Math.max(dfs(i - 1, j, 1), dfs(i - 1, j, 0) - prices[i]);
    }

    /**
     * 2.迭代
     */
    public int maxProfit12(int[] prices) {
        int n = prices.length;
        int[][][] f = new int[n + 1][3][2];
        for (int j = 0; j < f[0].length; j++) {
            f[0][j][1] = Integer.MIN_VALUE;
        }
        for (int i = 0; i < n; i++) {
            f[i][0][0] = Integer.MIN_VALUE;
            f[i][0][1] = Integer.MIN_VALUE;
            for (int j = 0; j < 2; j++) {
                f[i + 1][j + 1][0] = Math.max(f[i][j + 1][0], f[i][j][1] + prices[i]);
                f[i + 1][j + 1][1] = Math.max(f[i][j + 1][1], f[i][j + 1][0] - prices[i]);
            }
        }
        return f[n][2][0];
    }

    /**
     * 4.空间优化
     */
    public int maxProfit14(int[] prices) {
        int[][] f = new int[3][2];
        for (int j = 0; j < f[0].length; j++) {
            f[j][1] = Integer.MIN_VALUE;
        }
        f[0][0] = Integer.MIN_VALUE;
        for (int price : prices) {
            for (int j = 0; j < 2; j++) {
                f[j + 1][0] = Math.max(f[j + 1][0], f[j][1] + price);
                f[j + 1][1] = Math.max(f[j + 1][1], f[j + 1][0] - price);
            }
        }
        return f[2][0];
    }

    /*
      二、线性DP（枚举选哪个）注：此方法所有案例均会超时
     */

    /**
     * 1.递归
     */
    public int maxProfit21(int[] prices) {
        this.prices = prices;
        int n = prices.length;
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        int min = prices[i];
        for (int j = 0; j < i; j++) {
            if (prices[j] < min) min = prices[j];
        }
        if (prices[i] <= min) return dfs(i - 1);
        else return Math.max(prices[i] - min, dfs(i - 1));
    }

    /**
     * 2.迭代
     */
    public int maxProfit22(int[] prices) {
        int n = prices.length;

        int[] f = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int min = prices[i];
            for (int j = 0; j < i; j++) {
                if (prices[j] < min) min = prices[j];
            }
            if (prices[i] <= min) f[i + 1] = f[i];
            else f[i + 1] = Math.max(prices[i] - min, f[i]);
        }
        return f[n];
    }

    /**
     * 4.空间优化
     */
    public int maxProfit24(int[] prices) {
        int n = prices.length;

        int f0, f1 = 0;
        for (int i = 0; i < n; i++) {
            f0 = f1;
            int min = prices[i];
            for (int j = 0; j < i; j++) {
                if (prices[j] < min) min = prices[j];
            }
            if (prices[i] > min) {
                f1 = Math.max(prices[i] - min, f0);
            }
        }
        return f1;
    }

    /*
      三、贪心
     */
    public int maxProfit3(int[] prices) {
        int ans = 0;
        int min = prices[0];

        for (int price : prices) {
            if (price < min) min = price;
            else if (price > min) ans = Math.max(price - min, ans);
        }

        return ans;
    }
}
